#!/usr/bin/python
from __future__ import division
import sys
from blist import blist
#must install blist. sudo pip/apt-get install blist

#collaborators: Sana Imam, Ryan Allan 

intersectionFound = False

#introduce new structures to appease Jack 
class Point: 
	x = 0
	y = 0

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def lessThan(self, otherPoint):
		if self.x<otherPoint.x:
			return True
		elif self.x>otherPoint.x:
			return False
		elif self.y<otherPoint.y:
			return True 
		else:
			return False

class Vector: 
	xCompon = 0
	yCompon = 0 

	#vector from A to B
	def __init__(self, pointA, pointB):
		self.xCompon = pointB.x - pointA.x 
		self.yCompon = pointB.y - pointA.y 


class Flag: 
	x = 0
	y = 0
	slope = 0
	color = "Blank"
	flagType = "none"
	owner = None

	def __init__(self, x, y, slope, color, flagType, owner):
		self.x = x
		self.y = y
		self.slope = slope
		self.color = color 
		self.flagType = flagType
		self.owner = owner

def switchFlags(flagA, flagB): 
	#1 means switch, -1 means don't
	if flagA.x < flagB.x:
		return -1
	elif flagA.x > flagB.x:
		return 1 
	elif flagA.y < flagB.y:
		return -1 
	elif flagA.y > flagB.y: 
		return 1 
	elif flagA.flagType == "terminal" and flagB.flagType == "start":
		return -1 
	elif flagA.flagType == "start" and flagB.flagType == "terminal":
		return 1 
	elif flagA.slope > flagB.slope: 
		return -1
	elif flagA.slope < flagB.slope: 
		return 1
	elif flagA.color == "Blue" and flagB.color == "Red":
		return -1 
	elif flagA.color == "Red" and flagB.color == "Blue":
		return 1
	else: 
		return 0
		#return "dude, stop messin' around. Overlapping lines of same color."

#STILL NEED TO ADD COMPARISON FOR IF POINT LEFT, RIGHT, OR ON LINE. Don't know why. 
class Segment:
	firstPoint = Point(0, 0)
	secondPoint = Point(0, 0)
	color = "Blank"
	startFlag = Flag(0,0,0,"Blank","None",None)
	terminalFlag = Flag(0,0,0,"Blank","None",None)
	flagsSwapped = False
	segmentNumber = 0 

	def __init__(self, pointA, pointB, inputColor, segmentNumber):
		self.firstPoint = pointA
		self.secondPoint = pointB
		self.color = inputColor
		self.segmentNumber = segmentNumber
		self.createFlags(self.firstPoint,self.secondPoint,self.color)

	def createFlags(self,firstPoint,secondPoint,inputColor):
		#calculate slope
		if (firstPoint.x - secondPoint.x) == 0:
			slope = float("inf")
		else: 
			slope = (firstPoint.y - secondPoint.y) / (firstPoint.x - secondPoint.x)
		if(firstPoint.lessThan(secondPoint)): #then firstPoint is startFlag
			self.startFlag = Flag(firstPoint.x,firstPoint.y, slope, self.color, "Start" ,self) 
			self.terminalFlag = Flag(secondPoint.x, secondPoint.y, slope, self.color, "Terminal" , self)
		else:
			self.terminalFlag = Flag(firstPoint.x,firstPoint.y,slope,self.color, "Terminal" ,self) 
			self.startFlag = Flag(secondPoint.x, secondPoint.y, slope, self.color, "Start", self)
			flagsSwapped = True

	def relationToPoint(self,point):
		#use cross product to determine relation
		crazyCrossProd = ((self.secondPoint.x - self.firstPoint.x) * (point.y - self.firstPoint.y) - (self.secondPoint.y - self.firstPoint.y) * (point.x - self.firstPoint.x))
		if crazyCrossProd>0:
			return "Left"
		elif crazyCrossProd<0:
			return "Right"
		else:
			if self.firstPoint.y == float("inf"):
				return "Right"
			elif self.firstPoint.y == float("-inf"):
				return "Left"
			return "On Line"

	def __str__(self):
		return "({0},{1}),({2},{3})".format(self.firstPoint.x, self.firstPoint.y, self.secondPoint.x, self.secondPoint.y)


def outerProduct(vectorA, vectorB):
	return (vectorA.xCompon * vectorB.yCompon) - (vectorA.yCompon * vectorB.xCompon)

def determineIfIntersects(segmentA, segmentB):
	#see CLRS 33 for more info. 
	P_R = Vector(segmentA.firstPoint, segmentB.firstPoint)
	P_S = Vector(segmentA.firstPoint, segmentB.secondPoint)
	P_Q = Vector(segmentA.firstPoint, segmentA.secondPoint)
	Q_R = Vector(segmentA.secondPoint, segmentB.firstPoint)
	S_R = Vector(segmentB.secondPoint, segmentB.firstPoint)

	PR_times_PQ = outerProduct(P_R,P_Q)
	PS_times_PQ = outerProduct(P_S,P_Q)
	PR_times_SR = outerProduct(P_R,S_R)
	QR_times_SR = outerProduct(Q_R,S_R)

	return (PR_times_PQ * PS_times_PQ <0 and PR_times_SR * QR_times_SR <0)

def orderOfSegments(segmentA, segmentB): 
	if segmentB.relationToPoint(segmentA.firstPoint) == "Left":
		return -1
	elif segmentB.relationToPoint(segmentA.firstPoint) == "Right":
		return 1
	else:
		return 0

numberOfRuns = sys.argv[2] 

with open(sys.argv[1], 'r') as testFile:
  firstLine = testFile.readline()
  numberOfRed = int(firstLine.split()[0])
  numberOfBlue = int(firstLine.split()[1])
  numberOfProposedCrosses = int(firstLine.split()[2])

  blueLines = []
  redLines = []

  for incrementer in range(0,numberOfRed):
  	nextLine = testFile.readline()
  	redLines.append([nextLine.split()[0],nextLine.split()[1],nextLine.split()[2],nextLine.split()[3]])

  for incrementer in range(0,numberOfBlue):
  	nextLine = testFile.readline()
  	blueLines.append([nextLine.split()[0],nextLine.split()[1],nextLine.split()[2],nextLine.split()[3]])

segmentNumber = 1
allSegments = [] 

for blueLine in blueLines:

	blueA = Point(int(blueLine[0]),int(blueLine[1]))
	blueB = Point(int(blueLine[2]),int(blueLine[3]))
	blueSegment = Segment(blueA, blueB, "Blue", segmentNumber)
	allSegments.append(blueSegment)
	segmentNumber = segmentNumber + 1

segmentNumber = 1

for redLine in redLines:

	redA = Point(int(redLine[0]),int(redLine[1]))
	redB = Point(int(redLine[2]),int(redLine[3]))
	redSegment = Segment(redA, redB, "Red", segmentNumber)
	allSegments.append(redSegment)
	segmentNumber = segmentNumber + 1

sortedFlags = sorted([segment.startFlag for segment in allSegments] + [segment.terminalFlag for segment in allSegments], cmp=switchFlags)

#for flag in sortedFlags:
#	print "{0} {1} {2}".format(flag.owner.segmentNumber,flag.color,flag.flagType)

#Updated SI4 to use efficient data structure. 
listDataStructure = blist()
topSentinel = Segment(Point(float("-inf"),float("inf")),Point(float("inf"),float("inf")),"Not relevant",0)
bottomSentinel = Segment(Point(float("-inf"),float("-inf")),Point(float("inf"),float("-inf")),"Not relevant",0)
listDataStructure.append(topSentinel)
listDataStructure.append(bottomSentinel)
listDataStructure.sort(cmp=orderOfSegments)

segmentsAccountingBreaks = []
'''
for i in range(0,int(numberOfRuns)):
	for flag in sortedFlags:
		for existingSegment in allSegments:
			if existingSegment.relationToPoint(Point(flag.x,flag.y))=="On Line" and existingSegment!=flag.owner and flag.slope != existingSegment.startFlag.slope:
					#segmentsAccountingBreaks = [seg for seg in segmentsAccountingBreaks if (seg.segmentNumber!=existingSegment.segmentNumber and seg.color!=existingSegment.color)]
					firstSegment = Segment(existingSegment.firstPoint,Point(flag.x,flag.y),existingSegment.color,existingSegment.segmentNumber)
					secondSegment = Segment(Point(flag.x,flag.y),existingSegment.secondPoint,existingSegment.color,existingSegment.segmentNumber)
					print "first seg:",firstSegment
					print "first seg:",second
					#add 4 flags of those segments to flagsAccountingBreaks
					segmentsAccountingBreaks.extend([firstSegment,secondSegment])
			
		if flag.owner not in segmentsAccountingBreaks:
			print "added: ",flag.owner
			segmentsAccountingBreaks.append(flag.owner)
'''
'''
for i in range(0,int(numberOfRuns)):
	#intersectionFound = False
	for flag in sortedFlags:
		#print "----"
		for existingSegment in listDataStructure:
				#print existingSegment
				if existingSegment.relationToPoint(Point(flag.x,flag.y))=="On Line" and existingSegment!=flag.owner and flag.slope != existingSegment.startFlag.slope:
					#if flag.owner.startFlag in sortedFlags:
					#	sortedFlags.remove(flag.owner.startFlag)
					#if flag.owner.terminalFlag in sortedFlags:
					#	sortedFlags.remove(flag.owner.terminalFlag)
					#remove the two flags that belong to the existingSegment
					segmentsAccountingBreaks = [seg for seg in segmentsAccountingBreaks if (seg.segmentNumber!=existingSegment.segmentNumber)]
					#print segmentsAccountingBreaks
					#create the two new segments
					firstSegment = Segment(existingSegment.firstPoint,Point(flag.x,flag.y),existingSegment.color,existingSegment.segmentNumber)
					secondSegment = Segment(Point(flag.x,flag.y),existingSegment.secondPoint,existingSegment.color,existingSegment.segmentNumber)
					#add 4 flags of those segments to flagsAccountingBreaks
					segmentsAccountingBreaks.extend([firstSegment,secondSegment])


		#problem is I'm retaining the guys that get cut
		if all(flag.owner.segmentNumber != seg.segmentNumber for seg in segmentsAccountingBreaks):
			segmentsAccountingBreaks.append(flag.owner)

		if flag.flagType=="Start":
			listDataStructure.append(flag.owner)
			#listDataStructure.sort(cmp=orderOfSegments) #these don't take long with this data struct. #
			#indexOfInsertedElement = listDataStructure.index(flag.owner)
			#print flag.owner
			#if determineIfIntersects(listDataStructure[indexOfInsertedElement],listDataStructure[indexOfInsertedElement+1]) or determineIfIntersects(listDataStructure[indexOfInsertedElement],listDataStructure[indexOfInsertedElement-1]) :
				#intersectionFound = True
		else: 
			if flag.owner in listDataStructure:
				listDataStructure.remove(flag.owner)
	#if intersectionFound is False:
	#	print "VERIFIED"

'''
for i in range(0,int(numberOfRuns)):
	#intersectionFound = False
	for flag in sortedFlags:
		#print "----"
		for existingSegment in listDataStructure:
				#print existingSegment
				if existingSegment.relationToPoint(Point(flag.x,flag.y))=="On Line" and existingSegment!=flag.owner and flag.slope != existingSegment.startFlag.slope:
					#if flag.owner.startFlag in sortedFlags:
					#	sortedFlags.remove(flag.owner.startFlag)
					#if flag.owner.terminalFlag in sortedFlags:
					#	sortedFlags.remove(flag.owner.terminalFlag)
					#remove the two flags that belong to the existingSegment
					segmentsAccountingBreaks = [seg for seg in segmentsAccountingBreaks if (seg.segmentNumber!=existingSegment.segmentNumber)]
					#print segmentsAccountingBreaks
					#create the two new segments
					firstSegment = Segment(existingSegment.firstPoint,Point(flag.x,flag.y),existingSegment.color,existingSegment.segmentNumber)
					secondSegment = Segment(Point(flag.x,flag.y),existingSegment.secondPoint,existingSegment.color,existingSegment.segmentNumber)
					#add 4 flags of those segments to flagsAccountingBreaks
					segmentsAccountingBreaks.extend([firstSegment,secondSegment])

		if all(flag.owner.segmentNumber != seg.segmentNumber for seg in segmentsAccountingBreaks):
			#print "added: ",flag.owner
			segmentsAccountingBreaks.append(flag.owner)

		if flag.flagType=="Start":
			listDataStructure.append(flag.owner)
			#listDataStructure.sort(cmp=orderOfSegments) #these don't take long with this data struct. #
			#indexOfInsertedElement = listDataStructure.index(flag.owner)
			#print flag.owner
			#if determineIfIntersects(listDataStructure[indexOfInsertedElement],listDataStructure[indexOfInsertedElement+1]) or determineIfIntersects(listDataStructure[indexOfInsertedElement],listDataStructure[indexOfInsertedElement-1]) :
				#intersectionFound = True
		else: 
			if flag.owner in listDataStructure:
				listDataStructure.remove(flag.owner)
	#if intersectionFound is False:
	#	print "VERIFIED"


#re-sort with additions
#flagsAccountingBreaks = sorted(flagsAccountingBreaks, cmp=switchFlags)
for segment in segmentsAccountingBreaks:
	if segment.color == "Blue":
		print "{0} {1} {2} {3}".format(segment.startFlag.x,segment.startFlag.y,segment.terminalFlag.x,segment.terminalFlag.y)